# 反转链表

# 迭代法反转整个链表：
def reverse_list(head):
    pre, cur = None, head
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre


# 递归法反转整个链表：
def recure_reverse_list(head):
    if not head.next:
        return head
    last = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return last


# 递归反转部分链表
def recure_reverse_m_n(head, m, n):
    successor = None
    # 递归反转前n个节点：
    def recure_recerse_n(head, n):
        if n == 1:
            # 记录尾部最后一节点的后继节点
            successor = head.next
            return head
        last = recure_recerse_n(head.next, n - 1)
        head.next.next = head
        head.next = successor
        return last
    # 基本情况：
    if m == 1:
        return recure_recerse_n(head, n)
    head.next = recure_reverse_m_n(head.next, m - 1, n - 1)
    return head


# 迭代 K 个一组反转链表
# 先使用迭代法反转区间[a, b)的元素
def reverse_interval(a, b):
    pre = None
    cur = a
    nxt = a
    while cur != b:
        nxt = cur.nxt
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

def reverse_k_group(head, k):
    if not head:
        return None
    a = b = head
    for i in range(k):
        # 不足k个，不进行反转
        if not b:
            return head
        b = b.next
    new_head = reverse_interval(a, b)
    a.next = reverse_k_group(b, k)
    return new_head